# 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的
# 唯一组合。 
# 
#  candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 
# 
#  对于给定的输入，保证和为 target 的唯一组合数少于 150 个。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入: candidates = [2,3,6,7], target = 7
# 输出: [[7],[2,2,3]]
#  
# 
#  示例 2： 
# 
#  
# 输入: candidates = [2,3,5], target = 8
# 输出: [[2,2,2,2],[2,3,3],[3,5]] 
# 
#  示例 3： 
# 
#  
# 输入: candidates = [2], target = 1
# 输出: []
#  
# 
#  示例 4： 
# 
#  
# 输入: candidates = [1], target = 1
# 输出: [[1]]
#  
# 
#  示例 5： 
# 
#  
# 输入: candidates = [1], target = 2
# 输出: [[1,1]]
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= candidates.length <= 30 
#  1 <= candidates[i] <= 200 
#  candidate 中的每个元素都是独一无二的。 
#  1 <= target <= 500 
#  
#  Related Topics 数组 回溯 
#  👍 1585 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def dfs(remain, combine, idx):
            if idx == len(candidates):
                return
            if remain == 0:
                res.append(list(combine))
                return
            dfs(remain, combine, idx + 1)
            if remain - candidates[idx] >= 0:
                combine.append(candidates[idx])
                dfs(remain - candidates[idx], combine, idx)
                combine.pop()

        dfs(target, [], 0)
        return res


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 所有可行: 搜索回溯
# 回溯: dfs 走下去, 再返回
#     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
#         res = []
#
#         def dfs(remain: int, combine: List[int], idx: int) -> None:
#             if idx == len(candidates):
#                 return
#             if remain == 0:
#                 # 新建list返回, combine 重复利用
#                 res.append(list(combine))
#                 return
#             # 跳过当前数
#             dfs(remain, combine, idx + 1)
#             # 选择当前数
#             if remain - candidates[idx] >= 0:
#                 combine.append(candidates[idx])
#                 # 当前元素依旧会被选择, 故 idx依旧递归
#                 dfs(remain - candidates[idx], combine, idx)
#                 combine.pop()
#
#         dfs(target, [], 0)
#         return res
#
if __name__ == '__main__':
    s = Solution()
    candidates = [2, 3, 5]
    target = 8
    r1 = s.combinationSum(candidates, target)
    e1 = [[3, 5], [2, 3, 3], [2, 2, 2, 2]]
    assert r1 == e1, r1
